package com.breeze.leetcode;


// TODO: 归并完成排序链表

/**
 * https://leetcode-cn.com/problems/sort-list/
 * 148. 排序链表
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 */
public class LeetCode148 {

    /**
     * 方法一  归并排序（递归法）
     *
     * 空间复杂度：O(nlogn)
     * 时间复杂度：O(logn)
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // step1. 分割 cut
        // 通过快慢指针找到链表中点，奇数个为中心节点，偶数个为中心左边的节点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow 即是分割点
        ListNode tmp = slow.next; // 分割的后边链表
        slow.next = null; // 断开前后链表

        head = sortList(head);
        tmp = sortList(tmp);
        // step2. 归并
        return merge(head, tmp);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead;
        while (left != null && right != null) {
            if (left.val < right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        temp.next = left != null ? left : right;
        return dummyHead.next;
    }

    /**
     * 方法二：TODO 归并排序（从底至顶直接合并），非递归，空间复杂度降至O(1)
     * @param head
     * @return
     */
    public ListNode sortList2(ListNode head) {
        return null;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        // 测试1
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        LeetCode148 leetCode148 = new LeetCode148();
        ListNode res = leetCode148.sortList(head);
        foreach(res);
        // 测试2
        ListNode head2 = new ListNode(-1);
        head2.next = new ListNode(5);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(0);
        ListNode res2 = leetCode148.sortList(head2);
        foreach(res2);
    }

    public static void foreach(ListNode node) {
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }
}
